# 第3节堆——神奇的优先队列

# 最小堆（小顶推）：所有的父节点都要比子节点小
# 最大堆（大顶推）：所有的父节点都要比子节点大

n = 14  # 用来存储堆中元素的个数，也就是堆的大小
h = [0 for i in range(0, 15)]  # 用数组存储二叉树


# 交换数组的位置
def swap(t, i):
    temp = h[t]
    h[t] = h[i]
    h[i] = temp


# 向下调整
def sift_down(i: int):
    t = 0  # 记录最小节点
    flag = 0  # flag用来标记是否需要向下调整
    # 当i节点有子节点（至少有子节点的情况）并且需要继续调整的时候，循环执行
    while i * 2 <= n and flag == 0:
        if h[i] > h[i * 2]:
            t = i * 2
        else:
            t = i
        # 如果有右节点
        if i * 2 + 1 <= n:
            if h[t] > h[i * 2 + 1]:
                t = i * 2 + 1
        # 如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
        if t != i:
            swap(t, i)
            i = t  # 更新i为刚才与它交换的儿子结点的编号、便于接下来继续向下调整
        else:
            flag = 1  # 否则说明当前的父结点已经比两个子结点都要小了，不需委再进行调整了


# 向上调整
def siftup(i: int):  # 专入一个霭要向上调整的结点编号i
    flag = 0
    if i == 1:
        return
    while i != 1 and flag == 0:
        if h[i] < h[i // 2]:
            swap(i, i // 2)
        else:
            flag = 1
        i = i // 2  # 当前节点的父节点的编号


a = [0, 99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92]
print(a)
for i in range(1, n + 1):
    h[i] = a[i]
    siftup(i)
print(h)
# 更快的方法，直接把数放在一个完全二叉树
h = a
i = n // 2
while i >= 1:
    sift_down(i)
    i -= 1
print(h)


# 删除最大的元素
def delete_max():
    global n
    t = h[1]
    h[1] = h[n]
    n -= 1
    sift_down(1)
    return t


# 小顶堆排序
for i in range(1, n + 1):
    print('%d' % delete_max(), end=' ')
